/* atom.c - implement string atoms.
 */
#include "atom.h"

typedef struct  TAtom
    {
    const char* String;
    int         RefCount;
    unsigned    Hash;
    struct TAtom*   Next;
    }           TAtom;

static TAtom*   FreeList;       /* list of free TAtoms      */
static TAtom**  HashTable;      /* hash table of all TAtoms */
static unsigned HashSize;       /* size of hash table       */


/* AtomNew() - return pointer to empty atom.
 */
static
TAtom*      AtomNew(void)
    {
    TAtom*      Result;

    /* if freelist is empty, better put something on it */
    if(FreeList == NULL)
        {
        unsigned    iAtom;
        unsigned    BlockCount = (1024*4)/sizeof(TAtom);

        FreeList    = calloc(BlockCount, sizeof(TAtom));
        assert(FreeList != NULL);
    
        /* link together atoms in new block to form new free list */
        for(iAtom = 0; iAtom < (BlockCount-1); ++iAtom)
            FreeList[iAtom].Next    = &FreeList[iAtom+1];
        /* first time through, need to allocate hash table */
        if(HashTable == NULL)
            {
            HashSize    = 137;  /* prime number so mod does some scattering */
            HashTable   = calloc(HashSize, sizeof(TAtom*));
            assert(HashTable != NULL);
            }
        }

    /* now free list is not empty */
    Result      = FreeList;
    FreeList    = Result->Next;

    return Result;
    }


/* HashString() - return hash from string; nothing fancy.
 */
static unsigned HashString(const char* Str)
    {
    unsigned    Hash    = 0xFEAD;

    while(*Str)
        {
        Hash    = (Hash * 8) ^ *Str++;
        }
    }

/* AtomCreate() - create a new atom from a string (or find an existing atom!)
 */
ATOM        AtomCreate(const char* String)
    {
    unsigned    Hash    = HashString(String);
    TAtom**     Ptr     = &HashTable[Hash % HashTableSize];
    ATOM        Result  = NULL;

    /* search linked-list in hash table */
    while(*Ptr)
        {
        /* if we found a match */
        if((*Ptr)->Hash == Hash && !strcmp(String, (*Ptr)->String))
            {
            Result  = (ATOM)(*Ptr);
            break;
            }
        else
            Ptr = &((*Ptr)->Next);
        }

    if(Result == NULL)
        {
        TAtom*  New = AtomNew();

        New->Hash   = Hash;
        New->String = String;
        New->Next   = HashTable[Hash % HashTableSize];
        Result      = (ATOM)New;
        break;
        }
    }


void        AtomDeref(ATOM Atom);
ATOM        AtomRef(ATOM Atom);
ATOM        AtomFind(const char* String);
const char* AtomString(ATOM Atom);

